﻿/**********************************************/
/*Project: CRF#                               */
/*Author: Zhongkai Fu                         */
/*Email: fuzhongkai@gmail.com                 */
/**********************************************/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CRFSharp
{
    public class CrfTag
    {
        int FORWARD_BACKWARD_UNDO = 0;
        int FORWARD_BACKWARD_DONE = 1;

      
        //概率计算函数
        double toprob(Node n, double Z)
        {
            return Math.Exp(n.alpha + n.beta - (float)(n.cost) / Utils.CONV_INT_FACTOR - Z);
        }

        //当vlevel=0并且nbest=1时，即只需要输出最优的结果并且不需要得到概率值时，forward-backward算法和A*算法不进行，viterbi算法后直接得到结果。此时速度是最快的
        uint vlevel_; //是否需要概率计算, 0为不需要概率计算，>0为需要
        uint nbest_; //需要输出多少个结果序列

        double cost_;  //路径得分
        double Z_;  //用于计算概率值

        //以下部分为从模型中获取的指针和变量，以加速运算过程
        CrfModel model;
        List<string> unigram_templs_;
        List<string> bigram_templs_;
        public uint ysize;
        List<int> alpha_int_;
        double cost_factor_;
        //从模型获取部分结束于此

        uint word_num; //要标注的词数
        uint xsize_;

        List<List<int>> feature_cache_; //保存特征函数的id
        int feature_cache_size;

        List<List<Node>> node_; //节点矩阵

        Node node(int i, int j)
        {
            return node_[i][j];
        }

      //  List<List<Node>> node; //状态节点。代替原来的无向图, size = crf_max_word_num * ysize
        int[] result_; //结果取值, size = crf_max_word_num

        Heap heap_queue; //使用最小堆求取next result

        int tag_init_stat; //tag初始化状态位
        int forward_backward_stat; //前向后向过程运行状态，0为未运行，1为已经运行
        //my add 数据结构

        public static uint crf_max_word_num;
        public static uint crf_max_word_len;
        public static uint max_nbest;

        void set_node(int i, int j, ref List<int> f)
        {
            node_[i][j].lpath.Clear();
            node_[i][j].rpath.Clear();
            node_[i][j].x = i;
            node_[i][j].y = j;
            node_[i][j].fvector = f;
        }

        //简单化为单列标注，去掉了char_freelist_，直接存放到x_中，减少x_的层级
        public List<List<string>> x_; //保存词本身的数组, size = crf_max_word_num * crf_max_word_len

        public CrfTag(uint this_max_nbest = Utils.DEFAULT_MAX_NBEST, uint this_crf_max_word_num = Utils.DEFAULT_CRF_MAX_WORD_NUM, uint this_crf_max_word_len = Utils.DEFAULT_CRF_MAX_WORD_LEN)
        {
            crf_max_word_num = this_crf_max_word_num;
            crf_max_word_len = this_crf_max_word_len;
            vlevel_ = 0;
            nbest_ = 0;
            cost_ = 0.0;
            Z_ = 0;
            model = null;
            unigram_templs_ = null;
            ysize = 0;
            alpha_int_ = null;
            cost_factor_ = 0.0;
            word_num = 0;
            heap_queue = null;
            node_ = null;
            x_ = null;
            result_ = null;
            max_nbest = this_max_nbest;
            tag_init_stat = Utils.TAG_INIT_UNFINISH;
            forward_backward_stat = FORWARD_BACKWARD_UNDO;

            feature_cache_ = null;
            feature_cache_size = 0;
        }


        void set_crf_max_word_num(uint this_crf_max_word_num)
        {
            crf_max_word_num = this_crf_max_word_num;
        }

        void set_this_crf_max_word_len(uint this_crf_max_word_len)
        {
            crf_max_word_len = this_crf_max_word_len;
        }

        //判断该序列是否为空
        bool empty()
        {
            if (word_num == 0)
                return true;
            else
                return false;
        }

        //获取类型数
        uint get_ysize()
        {
            return ysize;
        }

        //获取序列的词数
        public uint get_word_num()
        {
            return word_num;
        }

        //获取cost
        double cost() { return cost_; }
        //获取Z值
        double get_Z() { return Z_; }


        public double prob(int i)
        {
            if (forward_backward_stat == FORWARD_BACKWARD_UNDO)
            {
                if (forwardbackward() != 0)
                {
                    return -1;
                }
            }
            return toprob(node_[i][result_[i]], Z_);
        }

        //获取第i个词的类别
        int result(int i) { return result_[i]; }
        //获取第i个词的类别		
        public int y(int i) { return result_[i]; }

        //获取第i类的字符表示
        public string yname(int i) { return model.y(i); }

        //获取vlevel
        public uint get_vlevel()
        {
            return vlevel_;
        }

        //获取nbest
        public uint get_nbest()
        {
            return nbest_;
        }

        //设置vlevel
        public void set_vlevel(uint vlevel_value)
        {
            vlevel_ = vlevel_value;
        }

        //设置nbest
        public void set_nbest(uint nbest)
        {
            if (nbest < max_nbest)
            {
                nbest_ = nbest;
            }
            else
            {
                nbest_ = max_nbest;
            }
        }

        //返回tag的初始化状态
        //返回TAG_INIT_FINISH为已经正确初始化，返回TAG_INIT_UNFINISH为未正确初始化
        int get_tag_init_stat()
        {
            return tag_init_stat;
        }


        string[] BOS = { "_B-1", "_B-2", "_B-3", "_B-4" };
        string[] EOS = { "_B+1", "_B+2", "_B+3", "_B+4" };


        void calcCost(Node n)
        {
            n.cost = 0;
            int c = 0;
            List<int> f = n.fvector;
            for (int i = 0; i < f.Count && f[i] != -1; i++)
            {
                c += (alpha_int_)[f[i] + n.y];
            }
            n.cost = (int)(cost_factor_ * c);
        }

        void calcCost(Path p)
        {
            int c = 0;
            List<int> f = p.fvector;
            for (int i = 0; i < f.Count && f[i] != -1; i++)
            {
                c += (alpha_int_)[(int)(f[i] + p.lnode.y * ysize + p.rnode.y)];
            }
            p.cost = (int)(cost_factor_ * c);
        }

        //使用模型初始化tag，必须先使用该函数初始化才能使用add和parse                                                                    
        //正常返回为0， 错误返回<0
        public int init_by_model(ref CrfModel model_p)
        {
            if (model_p.get_model_init_stat() != Utils.MODEL_INIT_FINISH)
            {
                return -1;
            }

            model = model_p;
            unigram_templs_ = model_p.get_unigram_templs();
            ysize = model_p.ysize();
            xsize_ = model_p.xsize();
            alpha_int_ = model_p.alpha_int();
            cost_factor_ = model_p.cost_factor();

            bigram_templs_ = model_p.get_bigram_templs();

            if (max_nbest > 1)
            {
                heap_queue = Utils.heap_init((int)(crf_max_word_num * ysize * ysize));
            }

            feature_cache_ = new List<List<int>>((int)(Utils.DEFAULT_CRF_MAX_WORD_NUM * 2));
            feature_cache_size = 0;
            int feature_cache_every_row_size = 0;
            if (unigram_templs_.Count > bigram_templs_.Count)
            {
                feature_cache_every_row_size = unigram_templs_.Count + 1;
            }
            else
            {
                feature_cache_every_row_size = bigram_templs_.Count + 1;
            }
            for (int i = 0; i < Utils.DEFAULT_CRF_MAX_WORD_NUM * 2; i++)
            {
                feature_cache_.Add(new List<int>(feature_cache_every_row_size));
                for (int j = 0; j < feature_cache_every_row_size; j++)
                {
                    feature_cache_[feature_cache_.Count - 1].Add(-1);
                }
            }

            node_ = new List<List<Node>>((int)Utils.DEFAULT_CRF_MAX_WORD_NUM);
            for (int i = 0; i < Utils.DEFAULT_CRF_MAX_WORD_NUM; i++)
            {
                node_.Add(new List<Node>((int)ysize));
                for (int j = 0; j < ysize; j++)
                {
                    node_[i].Add(new Node());
                }
            }


            tag_init_stat = Utils.TAG_INIT_FINISH;
            forward_backward_stat = FORWARD_BACKWARD_UNDO;
            return 0;
        }

        string get_index(ref string p, uint pos, ref int i)
        {
            if (p[i] != '[')
            {
                return null;
            }
            i++;

            int col = 0;
            int row = 0;

            int neg = 1;

            if (p[i] == '-')
            {
                neg = -1;
                i++;
            }

            while (i < p.Length)
            {
                if (p[i] >= '0' && p[i] <= '9')
                {
                    row = 10 * row + (p[i] - '0');
                }
                else if (p[i] == ',')
                {
                    i++;
                    goto NEXT1;
                }
                else return null;

                i++;
            }

        NEXT1:
            while (i < p.Length)
            {
                if (p[i] >= '0' && p[i] <= '9')
                {
                    col = 10 * col + (p[i] - '0');
                }
                else if (p[i] == ']')
                {
                    goto NEXT2;
                }
                else return null;

                i++;
            }
        NEXT2:
            row *= neg;

            if (row < -4 || row > 4 || col < 0 || col >= xsize_)
            {
                return null;
            }
            int idx = (int)(pos + row);
            if (idx < 0)
            {
                return BOS[-idx - 1];
            }
            if (idx >= word_num)
            {
                return EOS[idx - word_num];
            }

            return x_[idx][col];
        }

        int apply_rule(ref StringBuilder feature_function, string p, uint pos)
        {
            feature_function.Remove(0, feature_function.Length);
            string r;

            for (int i = 0; i < p.Length; i++)
            {
                if (p[i] == '%')
                {
                        i++;
                        switch (p[i])
                        {
                            case 'x':
                                i++;
                                r = get_index(ref p, pos, ref i);
                                if (r == null)
                                {
                                    return -1;
                                }
                                feature_function.Append(r);
                                break;
                            default:
                                return -1;
                        }
                }
                else
                {
                        feature_function.Append(p[i]);
                }
            }

            return 0;

        }


        public int buildFeatures()
        {
            int ret = 0;
            if (word_num <= 0)
            {
                return -1;
            }

            StringBuilder feature_function = new StringBuilder();
            int id = 0;
            int feature_cache_row_size = 0;
            for (uint cur = 0; cur < word_num; cur++)
            {
                feature_cache_row_size = 0;
                for (int i = 0; i < unigram_templs_.Count; i++)
                {
                    ret = apply_rule(ref feature_function, unigram_templs_[i], cur);
                    if (ret < 0)
                    {
                        return -1;
                    }

                    id = model.get_id(feature_function.ToString());
                    if (id != -1)
                    {
                        feature_cache_[feature_cache_size][feature_cache_row_size] = id;
                        feature_cache_row_size++;
                    }
                }
                feature_cache_[feature_cache_size][feature_cache_row_size] = -1;
                feature_cache_size++;
            }

            for (uint cur = 0; cur < word_num; cur++)
            {
                feature_cache_row_size = 0;
                for (int i = 0; i < bigram_templs_.Count; i++)
                {
                    ret = apply_rule(ref feature_function, bigram_templs_[i], cur);
                    if (ret < 0)
                    {
                        return -1;
                    }

                    id = model.get_id(feature_function.ToString());
                    if (id != -1)
                    {
                        feature_cache_[feature_cache_size][feature_cache_row_size] = id;
                        feature_cache_row_size++;
                    }
                }
                feature_cache_[feature_cache_size][feature_cache_row_size] = -1;
                feature_cache_size++;
            }

            return 0;

        }

        int rebuildFeatures()
        {
            int fid = 0;  
            for (int cur = 0; cur < word_num; cur++)
            {
                List<int> f = feature_cache_[fid++];
                for (int i = 0; i < ysize; i++)
                {
                    set_node(cur, i, ref f);
                }
            }

            for (int cur = 1; cur < word_num; cur++)
            {
                List<int> f = feature_cache_[fid++];
                for (int j = 0; j < ysize; ++j)
                {
                    for (int i = 0; i < ysize; ++i)
                    {
                        Path p = new Path();
                        p.add(node_[cur - 1][j], node_[cur][i]);
                        p.fvector = f;
                    }
                }
            }

            return 0;
        }


        public int initNbest()
        {
            int k = (int)word_num - 1;
            for (int i = 0; i < ysize; ++i)
            {
                QueueElement eos = Utils.allc_from_heap(ref heap_queue);
                eos.node = node_[k][i];
                eos.fx = -node_[k][i].bestCost;
                eos.gx = -node_[k][i].cost;
                eos.next = null;
                if (Utils.heap_insert(ref eos, ref heap_queue) < 0)
                {
                    return -1;
                }
            }
            return 0;
        }

        public int next()
        {
            if (tag_init_stat != Utils.TAG_INIT_FINISH)
            {
                return -1;
            }
            if (max_nbest == 1)
            {
                return -1;
            }

            while (!Utils.is_heap_empty(ref heap_queue))
            {
                QueueElement top = Utils.heap_delete_min(ref heap_queue);
                Node rnode = top.node;

                if (rnode.x == 0)
                {
                    for (QueueElement n = top; n != null; n = n.next)
                    {
                        result_[n.node.x] = n.node.y;
                    }
                    cost_ = top.gx;
                    return 0;
                }

                for (int i = 0; i < rnode.lpath.Count; i++)
                {
                    QueueElement n = Utils.allc_from_heap(ref heap_queue);
                    int x_num = (rnode.x) - 1;
                    n.node = rnode.lpath[i].lnode;
                    n.gx = -rnode.lpath[i].lnode.cost - rnode.lpath[i].cost + top.gx;
                    n.fx = -rnode.lpath[i].lnode.bestCost - rnode.lpath[i].cost + top.gx;
                    //          |              h(x)                 |  |  g(x)  |
                    n.next = top;
                    if (Utils.heap_insert(ref n, ref heap_queue) < 0)
                    {
                        return -1;
                    }

                }
            }
            return 0;
        }


        //清空tag, 释放占用的资源                                                                                                        
        //正常返回为0， 错误返回<0
        public int clear()
        {
            if (tag_init_stat != Utils.TAG_INIT_FINISH)
            {
                return -1;
            }

            model = null;
            unigram_templs_ = null;
            alpha_int_ = null;

            if (node_ != null)
            {
                for (int i = 0; i < crf_max_word_num; i++)
                {
                    if (node_[i] != null)
                    {
                        node_[i] = null;
                    }
                }
                node_ = null;
            }

            if (result_ != null)
            {
                result_ = null;
            }

            if (x_ != null)
            {
                for (int i = 0; i < crf_max_word_num; i++)
                {
                    if (x_[i] != null)
                    {
                        x_[i] = null;
                    }
                }
                x_ = null;
            }

         
            word_num = 0;
            Z_ = cost_ = 0.0;

            Utils.heap_clear(ref heap_queue);
            heap_queue = null;

            tag_init_stat = Utils.TAG_INIT_UNFINISH;

            return 0;
        }

        public int reset()
        {
            if (tag_init_stat != Utils.TAG_INIT_FINISH)
            {
                return -1;
            }
            word_num = 0;
            Z_ = cost_ = 0.0;
            feature_cache_size = 0;

            forward_backward_stat = FORWARD_BACKWARD_UNDO;
            Utils.heap_reset(ref heap_queue);
            return 0;
        }


        int buildLattice()
        {
            if (word_num == 0)
            {
                return -1;
            }

            rebuildFeatures();
            for (int i = 0; i < word_num; i++)
            {
                for (int j = 0; j < ysize; j++)
                {
                    calcCost(node_[i][j]);
                    List<Path> lpath = node_[i][j].lpath;
                    for (int k = 0; k < node_[i][j].lpath.Count; k++)
                    {
                        calcCost(lpath[k]);
                    }
                }
            }

            return 0;
        }

        public int forwardbackward()
        {
            if (word_num == 0)
            {
                return -1;
            }

            for (int i = 0; i < word_num; ++i)
            {
                for (int j = 0; j < ysize; ++j)
                {
                    node_[i][j].calcAlpha();
                }
            }

            for (int i = (int)word_num - 1; i >= 0; --i)
            {
                for (int j = 0; j < ysize; ++j)
                {
                    node_[i][j].calcBeta();
                }
            }

            Z_ = 0.0;
            for (int j = 0; j < ysize; ++j)
            {
                Z_ = Utils.logsumexp(Z_, node_[0][j].beta, j == 0);
            }
            forward_backward_stat = FORWARD_BACKWARD_DONE;
            return 0;
        }

        //标注输入串过程，输出存于result[]中。如果设置了nbest>1，之后可以通过next获取nbest结果                                           
        //正常返回为0， 错误返回<0
        public int viterbi()
        {
            Node best;
            int bestc;

            for (int i = 0; i < word_num; ++i)
            {
                for (int j = 0; j < ysize; ++j)
                {
                    bestc = Utils.INT_MIN;
                    best = null;
                    List<Path> lpath = node_[i][j].lpath;
                    for (int k = 0; k < node_[i][j].lpath.Count; k++)
                    {
                        int node_cost = lpath[k].lnode.bestCost + lpath[k].cost + node_[i][j].cost;

                        
                        if (node_cost > bestc)
                        {
                            bestc = node_cost;
                            best = lpath[k].lnode;
                        }
                    }

                    node_[i][j].prev = best;
                    node_[i][j].bestCost = (best != null) ? bestc : node_[i][j].cost;
                }
            }

            bestc = Utils.INT_MIN;
            best = null;
            int s = (int)word_num - 1;
            for (int j = 0; j < ysize; ++j)
            {
                if (bestc < node_[s][j].bestCost)
                {
                    best = node_[s][j];
                    bestc = node_[s][j].bestCost;
                }
            }

            for (Node n = best; n != null; n = n.prev)
            {
                result_[n.x] = n.y;
            }
            cost_ = -node_[(int)word_num - 1][result_[(int)word_num - 1]].bestCost;

            return 0;
        }
     
        public int add(ref List<List<string>> row_p)
        {
            if (tag_init_stat != Utils.TAG_INIT_FINISH)
            {
                return -1;
            }
            x_ = row_p;

            result_ = new int[row_p.Count];
            //for (int i = 0; i < row_p.Count; i++)
            //{
            //    result_.Add(0);
            //}
            word_num = (uint)x_.Count;

            return 0;
        }


       

        //标注输入串过程，输出存于result[]中。如果设置了nbest>1，之后可以通过next获取nbest结果                                           
        //正常返回为0， 错误返回<0	
        public int parse()
        {
            if (tag_init_stat != Utils.TAG_INIT_FINISH)
            {
                return -1;
            }
            int ret = 0;
            //1.无待标注元素则返回
            if (word_num == 0)
            {
                return 0;
            }


            //2. buildFeatures
            //标注序列的特征化
            ret = buildFeatures();
            if (ret < 0)
            {
                return -1;
            }


            ret = buildLattice();
            if (ret < 0)
            {
                return -1;
            }

            //4.forward-backward
            //当需要概率计算时，进行前向后向(forward-backward)算法
            if (vlevel_ == 1)
            {
                ret = forwardbackward();
                if (ret < 0)
                {
                    return -1;
                }
            }


            //5.viterbi
            //求取最优路径的viterbi算法
            ret = viterbi();
            if (ret < 0)
            {
                return -1;
            }

            //6.initNbest
            //	求nbest(n>1)时的数据结构初始化，此后可以调用next()来获取nbest结果
            if ((max_nbest > 1) && (nbest_ > 1))
            {  //如果只求1-best，不需要使用initNbest()和next()获取结果
                ret = initNbest();
                if (ret < 0)
                {
                    return -1;
                }

            }

            return 0;
        }

    }
}
